\documentclass[11pt, a4paper]{report}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage{array}
\usepackage{url}
\usepackage{a4wide}
\usepackage{caption}
\usepackage{color}
\usepackage{listings}
\usepackage{pdfpages}
\usepackage[pdftex,bookmarks=true]{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=black,
    urlcolor=black
}

\definecolor{gray80}{gray}{.8}
\lstdefinestyle{consola}
        {
         basicstyle=\scriptsize\bf\ttfamily,
         backgroundcolor=\color{gray80},
         frame=Ltb,
         framerule=0pt,
         aboveskip=0.5cm,
         framextopmargin=3pt,
     framexbottommargin=3pt,
%      framexleftmargin=0.4cm,
     framesep=0pt,
     rulesep=.4pt,
     rulesepcolor=\color{black},
     tabsize=2
}

\renewcommand{\captionfont}{\footnotesize}
\renewcommand{\captionlabelfont}{\bfseries}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\renewcommand*\familydefault{\sfdefault}


\usepackage{color}
\usepackage{listings}

\definecolor{gray}{gray}{0.5}
\definecolor{green}{rgb}{0,0.5,0}


\newcommand{\imgdir}{./img}
\graphicspath{{\imgdir/}}

\newcommand{\cod}[1]{\texttt{\bfseries #1}}
\newcommand{\reg}[1]{\texttt{\bfseries #1}}
\newcommand{\n}{\texttt{\ensuremath{\backslash}n}}
\newcommand{\0}{\texttt{\ensuremath{\backslash}0}}

\def\thesection{\arabic{section}}

%parámetros para fbox
\setlength\fboxsep{15pt}
\setlength\fboxrule{0.5pt}

\title{66.20 Organización de computadoras}
\author{Verónica Bukaczewski \and Ariel George}
\date{\today}


\begin{document}
\include{caratula}

%Cabeceras y pies de página
\pagestyle{fancy}
\lhead{}
%\lhead{\fancyplain{}{Organizaci\'on de computadoras 66.20 - Turno Jueves}}
\chead{}
%\rhead{\fancyplain{}{Trabajo Pr\'actico 2}}
\rhead{}
\lfoot{\scriptsize{66.20 Organización de computadoras - Turno jueves\\Trabajo
práctico 2 - 1er cuatrimestre 2011\\Verónica Bukaczewski(86954), Ariel George
(88024)}}
\cfoot{}
\rfoot{\\\thepage}
\renewcommand{\headrulewidth}{0pt}

\setcounter{page}{2}

\newpage
\thispagestyle{empty}
\tableofcontents

\newpage
\section{Introducción}
  En el presente trabajo pr\'actico se busc\'o familiarizarse con la medici\'on de comportamiento, utilizando herramientas de profiling, y con la estimaci\'on de par\'ametros de una memoria cach\'e, a partir de patrones de acceso y tasa de desaciertos al implementar un suite de benchmarking de memorias cach\'e.


\section{Resolución del problema}
  \subsection{Funci\'on main}
  Esta función se encarga de obtener las opciones de ejecución del programa utilizando la funci\'on getopt y, en base a eso, realizar una corrida del programa. \\
  Para la captura de los par\'ametros opcionales, se decidi\'o utilizar la funci\'on getopt\_long que trabaja como getopt salvo que tambi\'en acepta opciones largas, que empiezan por dos guiones.


  \subsection{Ejecucci\'on de Cachegrind}
  Cachegrind es una herramienta que viene incluida en el programa Valgrind, utilizado en los sistema Unix para detectar p\'erdidas de memoria (memory leaks). Para utilizar Cachegrind se le debe pasar un par\'ametro al Valgrind de la siguiente manera:
  \begin{lstlisting}[style=consola]
  $ valgrind --tool=cachegrind ejecutable
  \end{lstlisting}
  La informaci\'on generada por el cachegrind, se guarda por default en un archivo llamado cachegrind.out.PID (donde PID es el c\'odigo del proceso). Para modiﬁcar esto y generar un archivo con el nombre cachegrind out en el mismo directorio de ejecucci\'on, se debe hacer:
  \begin{lstlisting}[style=consola]
  $ valgrind --tool=cachegrind --cachegrind-out-file=cachegrind out ejecutable
  \end{lstlisting}
  Para simular una memoria cache espec\'ifica, hay que utilizar las opciones –I1, –D1 y –L2, pero en este caso la \'unica que nos interesa es –D1 ya que se requiere simular una cache de datos de nivel 1. Las caracter\'isticas de la cache se pasan separadas por comas, de esta manera: tama\~no , asociatividad , tama\~no de l\'inea. Por ejemplo, para nuestro caso, que deseamos simular una cache de 2048 bytes 4WSA de 64 bytes por bloque, se debe hacer:
  \begin{lstlisting}[style=consola]
  $ valgrind --tool=cachegrind --D1=2048,4,64 ejecutable
  \end{lstlisting}
  Para redigir la salida por pantalla del Valgrind (que informa la cantidad de misses, por ejemplo, a un archivo llamado logstdout out) se debe tipear:
  \begin{lstlisting}[style=consola]
  $ valgrind --log-file=logstdout out ejecutable
  \end{lstlisting}
  Si juntamos todas las opciones, tenemos que para cada uno de los cinco archivos ejecutables generados despu\'es de compilar, se debe invocar el valgrind de la siguiente manera:
  \begin{lstlisting}[style=consola]
  $ valgrind --tool=cachegrind --D1=2048,4,64 --cachegrind-out-file=cachegrind \
           out --log-file=logstdout out ./ejecutable
  \end{lstlisting}


  \subsection{Ejecucci\'on de cg\_annotate}
  Cg annotate es otra herramienta que provee valgrind para poder obtener un detallado informe sobre la cantidad de hits y misses de cache de cada l\'inea de codigo, y de cada funci\'on. Se debe generar la informaci\'on de debug como se aclar\'o anteriormente. Para ejecutar cg\_annotate, se debe hacer por consola:
  \begin{lstlisting}[style=consola]
  $ cg_annotate archivo --auto=yes
  \end{lstlisting}
  donde: archivo es el archivo de salida generado por cachegrind.                                                                      


  \subsection{C\'alculos realizados}
  Para poder corroborar que los resultados obtenidos eran correctos, se decidi\'o simular la memoria cach\'e, utilizando la herramienta {\bf Cachegrind}. 

  \subsubsection{C\'alculo del tama\~no del bloque de la memoria cach\'e}
  Para calcular el tama\~no del bloque de la memoria cach\'e, se realiza una corrida de un lazo simple, con la herramienta {\bf Valgrind} m\'odulo {\bf Cachegrind}. Luego, se corre el {\bf cg\_annotate}, observando s\'olo en la funci\'on lazo\_tamanio\_bloque que es donde se utiliza la memoria.
  Al finalizar la corrida de dicho lazo, accedimos a todos los bloques de la cache; entonces utilizando los resultados obtenidos de cg\_annotate, se realiza la divisi\'on entre la cantidad de accesos por escritura y la cantidad de misses por escritura.
  
  \subsubsection{C\'alculo del tama\~no de la memoria cach\'e}
  Para calcular el tama\~no de la memoria cach\'e, se supone una x cantidad de bloques que posee la memoria. Luego, se realiza la corrida de 100 lazos simples, cuyo tama\~no esta dado por la multiplicaci\'on del tama\~no bloque y la cantidad x de bloques. Se analiza la corrida con el 
  {\bf cg\_annotate}, observando s\'olo en la funci\'on lazo\_tamanio\_cache, entonces si la tasa de misses de escritura es menor o igual a la cantidad de bloques que se suposo, entonces no se han recorrido todos los bloques; por lo cual se aumenta la cantidad de bloques en potencia de dos y volvemos a ejecutar el lazo.

  \subsubsection{C\'alculo de la cantidad de v\'ias de la memoria cach\'e}
  Para calcular la cantidad de v\'ias de la memoria cach\'e, se supone una x cantidad de v\'ias que posee la memoria. Luego, se realiza la corrida de 100 lazos simples sobre una matriz, que tiene tantas columnas como el tama\~no de la memoria cache y tantas filas como cantidad de v\'ias que suponemos que tiene. Al finalizar el lazo, se accede a las primeras posiciones de cada una da las filas de la matriz, que es lo mismo que a cada primer bloque de cada v\'ia. Se analiza la corrida con el {\bf cg\_annotate}, si los \'ultimos accesos no producen misses en la cache entonces no hemos accedido a todos los bloques de cada v\'ia; por lo cual se aumenta la cantidad de v\'ias en potencia de dos y volvemos a ejecutar el lazo.

\section{Compilación}
 Para compilar el ejecutable debe ingresarse al directorio con los archivos fuentes y ejecutar make.


\section{Ejecutando el programa}
  Para ejecutar el programa, el comando a utilizar es:
\begin{lstlisting}[style=consola]
 $ ./tp2 [opciones]
\end{lstlisting}
 
 Opciones:
  \begin{description}
    \item [\cod{-}\cod{-D1=size,vias,blocksize}] simula una memoria de las caracteristicas dadas. 
    \item [\cod{-v}, \cod{-}\cod{-version}] imprime la versi\'on y finaliza.
    \item [\cod{-h}, \cod{-}\cod{-help}]     imprime la informaci\'on del comando y finaliza.
  \end{description}
 

\section{Casos de prueba}
A continuación se adjuntan capturas de la salida del programa simulando tres memorias caché diferentes. Una de 32 KiB, 4 vías y bloques de 32 Bytes (figura \ref{32768-4-32}), una del mismo tamaño y cantidad de vías pero con bloques de 64 Bytes (figura \ref{32768-4-64}) y finalmente una memoria caché de 2 KiB, 2 vías y bloques de 16 Bytes (figura \ref{2048-2-16}).
\begin{figure}[!ht]
  \centering
  \fbox{\includegraphics[width=250pt]{32768-4-32}}
  \caption{Salida del programa al simular una memoria caché de 32 KiB, 4 vías y bloques de 32 Bytes.}
  \label{32768-4-32}
\end{figure}

\begin{figure}[!ht]
  \centering
  \fbox{\includegraphics[width=250pt]{32768-4-64}}
  \caption{Salida del programa al simular una memoria caché de 32 KiB, 4 vías y bloques de 64 Bytes.}
  \label{32768-4-64}
\end{figure}

\begin{figure}[!ht]
  \centering
  \fbox{\includegraphics[width=250pt]{2048-2-16}}
  \caption{Salida del programa al simular una memoria caché de 2 KiB, 2 vías y bloques de 16 Bytes.}
  \label{2048-2-16}
\end{figure}

\section{Conclusiones}
Se realizó un programa que permite analizar los parámetros de una memoria caché. Esto permitió entender más sobre el análisis dinámico de un programa, del uso que hace de la memoria y cómo \emph{responde} la memoria caché a este uso. En este caso se trató de programas hechos especialmente para analizar la memoria caché, pero técnicas similares sirven para optimizar los programas.

\begin{thebibliography}{99}
	\bibitem{valgrind}
		Valgrind Developers,
		\emph{\textbf{Cachegrind user manual}}.
    \url{http://valgrind.org/docs/manual/cg-manual.html}
\end{thebibliography}

%APENDICES
\appendix
\newpage
\chapter*{Enunciado}
\addcontentsline{toc}{section}{Enunciado}
\includepdf[pages=1-3, scale=0.9, pagecommand={\thispagestyle{empty}}]{../TP2-1C-2011.pdf}

\end{document}
